/** @file List management routines */



/* Author: Ratish J. Punnoose, 2006
 * This file is part of TiROS, the Tickless Real-Time Operating System.
 * Copyright(c) 2006, 2007: Ratish J. Punnoose.
 * Copyright(c) 2006 Sandia Corporation. Under the terms of Contract
 * DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government retains
 * certain rights in this software. 
 * 
 * TiROS is free software; you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free
 * Software Foundation; either version 2 or (at your option) any later version.
 *
 * TiROS is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with TiROS; if not, write to the Free Software Foundation, Inc.,
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
 *
 * As a special exception, if other files instantiate templates or use macros
 * or inline functions from this file, or you compile this file and link it
 * with other works to produce a work based on this file, this file does not
 * by itself cause the resulting work to be covered by the GNU General Public
 * License. However the source code for this file must still be made available
 * in accordance with section (3) of the GNU General Public License.
 *
 * This exception does not invalidate any other reasons why a work based on
 * this file might be covered by the GNU General Public License.
 *
 */


/* There are several lists kept by TiROS
 * 1. A Ready list in order of priority.
 * 2. A Wait list in order of wake time.
 * 3. On each lock, there is a lock list in order of priority.
 */



/* There is no corresponding tr_llmgr.c, instead, the functions in
 * this file get directly inserted into tiros.c so that the compiler has
 * the ability to optimize and inline small functions to increase
 * efficiency.  Typically, this file is only included by tiros.c, but
 * it can also be included by user files, for getting debugging data
 * (internal Tiros data structures for list managment).  So we
 * distinguish when tiros.c includes this file as opposed to a user
 * file.*/


/** \addtogroup os_advanced @{   */

#ifdef TIROSINT_DATA_DEBUG

/** Structure to capture TiROS list management data for this sort
    method. */
typedef struct trlistdata {
	tid_t readylisthead;         /**< Index of readylist head */
	tid_t waitlisthead;          /**< Index of waitlist head  */
#if (TIROS_PRIO_SORT_METHOD == 1)
	/* This sort method uses an array based link list for sorting on
	 * priority. */
	tid_t * rdywt_listmeta;    /**< Pointer to rdy/wt list metadata */
	tid_t * lock_listmeta;    /**< Pointer to lock list metadata */
#else
/* We can add other methods for sorting the priority list in the
 * future. */
#error "TIROS_PRIO_SORT has illegal value in configuration."
#endif

} trlistdata_t;



/** Get the internal list data from tiros.
 * The list structure is defined in tr_llmgr.h
 * @param [out] lstdata   Provide tiros internal list management data
 * structures. */ 
void osint_getlistdata(trlistdata_t *  lstdata);
#endif
/** @} ---------------------------------------------------------- */











#ifdef TIROS_C
#  define LL_ELEM_TYPE  tid_t
#include "tr_ll.h"


/** Metadata for the ready/wait list
 * Wait list is always ordered in time. We keep a metadata list for
 * ordering it.  This is an array based linked list. 
 *
 * For  TIROS_PRIO_SORT_METHOD==1, where ready list is kept as a linked
 * list implemented within an array, we can use the same metadata as
 * the wait list, because a task is either in ready or wait state but
 * not both.  There is no memory overhead for maintaining the ready list
 * since it is already incurred for maintaining the wait list.
 * */
static tid_t  	rdywt_list_metadata[TIROS_MAX_PROCS];

/** The wait/sleep list arranged by wakeup time
 * The index to the head of the wait list.*/
static tid_t  waitlist;




#ifdef TIROS_USE_INLINE_GENERATORS
#  define PRIO_INLINE  static inline
#else
#  define PRIO_INLINE static
#endif


/** \name Priority_determination_functions_for_sorting_lists 
 * These functions conform to the prototype of prior_gt_t. @{ */

/** Order two tasks in relative priority
 * @param newobj  New task.
 * @param oldobj  Old task.
 * @return 1 if the new task has a higher priority , 0
 * otherwise */
PRIO_INLINE unsigned char prio_gtthan(ll_ind_t newobj, ll_ind_t oldobj);
PRIO_INLINE unsigned char prio_gtthan(ll_ind_t newobj, ll_ind_t oldobj)
{
	unsigned char ret_val;
	if ( TCBarray[newobj].eff_priority < 
	     TCBarray[oldobj].eff_priority){	
		ret_val = 1U;
	} else {
		ret_val = 0U;
	}
	return ret_val;
}

/**  Order two tasks in order of wakeup time.
 * @param newobj  New task.
 * @param oldobj  Old task.
 * @return 1 if the new task has an earlier waketime, 0
 * otherwise */
PRIO_INLINE unsigned char waketime_lessthan(ll_ind_t newobj, ll_ind_t oldobj);
PRIO_INLINE unsigned char waketime_lessthan(ll_ind_t newobj, ll_ind_t oldobj)
{
	return (unsigned char) 
		time_lessthan( &TCBarray[newobj].timeout,   
			       &TCBarray[oldobj].timeout);
}
/** @}  ------------------------------------------------------------ */

/**  @defgroup Priority Comparison functions.  Define a priority
 *  comparison based on 1.priority, 2. waketime @{ */
#ifdef TIROS_USE_INLINE_GENERATORS
LL_generator_func(LL_prio_add_prio_gtthan, prio_gtthan)
LL_generator_func(LL_prio_add_waketime, waketime_lessthan)
#else

#define LL_prio_add_prio_gtthan(lst, meta, elem) \
 LL_add_prio(lst, meta, elem, prio_gtthan)

#define LL_prio_add_waketime(lst, meta, elem) \
 LL_add_prio(lst, meta, elem, waketime_lessthan)

#endif
/** @} -------------------- */








/* Redundant declarations to satisfy stupid Misra-C */
static inline tid_t WT_list_head(void);
static inline tid_t WT_list_pop(void);
static inline void WT_list_rm(tid_t task);
static inline void WT_list_add(tid_t task);

static inline tid_t RDY_list_head(void);
static inline tid_t RDY_list_pop(void);
static inline void RDY_list_rm(tid_t task);
static inline void RDY_list_add(tid_t task);

static inline void LK_list_init(plist_t *locklisthead);
static inline tid_t LK_list_head(plist_t locklisthead);
static inline tid_t LK_list_pop(plist_t* locklisthead);
static inline void LK_list_rm(plist_t *locklisthead, tid_t task);
static inline void LK_list_add(plist_t *locklisthead, tid_t task);
static inline tid_t LK_list_next(plist_t *locklisthead, tid_t task);




/* Wait lists are always ordered by time */

static inline tid_t WT_list_head(void)
{
	return waitlist;
}

static inline tid_t WT_list_pop(void)
{
	return LL_pop_head(&waitlist, rdywt_list_metadata);
}

static inline void WT_list_rm(tid_t task)
{
	(void) LL_remove_elem(&waitlist, rdywt_list_metadata, task);
}

static inline void WT_list_add(tid_t task)
{
	LL_prio_add_waketime(&waitlist, rdywt_list_metadata, task);
}




/* There are three types of lists.
 * 1. The ready list - sorted by priority.
 * 2. The global wait list - sorted by time.
 * 3. The per resource, lock list - sorted by priority.
 */

#if (TIROS_PRIO_SORT_METHOD == 1) 
/** Metadata for the locklist.
 * This is the implementation of the "per lock" prioritized list.
 * However, since any single task can only be waiting for one lock at
 * any time (it may possess other locks but can only wait on one), we
 * can combine all the locklists for each lock into a global list.
 * This has low overhead.  Each lock maintains an index to the head of
 * the list. */ 
static tid_t  		lock_list_metadata[TIROS_MAX_PROCS];

/** The readylist arranged by task priority 
 * The index to the head of the ready list. */
static tid_t  readylist;




static inline tid_t RDY_list_head(void)
{
	return readylist;
}

static inline tid_t RDY_list_pop(void)
{
	tid_t rc;	
	rc =  LL_pop_head(&readylist, rdywt_list_metadata);	
	TR_MSG_TRACE_args('P', rc, readylist);
	return rc;
}

static inline void RDY_list_rm(tid_t task)
{
	(void) LL_remove_elem(&readylist , rdywt_list_metadata, task);
	TR_MSG_TRACE_args('R', task, readylist);
}

static inline void RDY_list_add(tid_t task)
{
	LL_prio_add_prio_gtthan(&readylist, rdywt_list_metadata, task);
	TR_MSG_TRACE_args('A', task, readylist);
}









static inline void LISTS_init(void)
{
	int i;
	for (i=0; i< TIROS_MAX_PROCS; i++) {
		rdywt_list_metadata[i] 		= ILLEGAL_ELEM;
		lock_list_metadata[i] 		= ILLEGAL_ELEM;
	}
	waitlist  = ILLEGAL_ELEM;
	readylist = ILLEGAL_ELEM;
}



static inline void LK_list_init(plist_t *locklisthead)
{
	*locklisthead = ILLEGAL_ELEM;
}

static inline tid_t LK_list_head(plist_t locklisthead)
{
	return locklisthead;
}
static inline tid_t LK_list_pop(plist_t* locklisthead)
{
	return LL_pop_head(locklisthead, lock_list_metadata);
}

static inline void LK_list_rm(plist_t *locklisthead, tid_t task)
{
	(void) LL_remove_elem(locklisthead, lock_list_metadata, task);
}

static inline void LK_list_add(plist_t *locklisthead, tid_t task)
{
	LL_prio_add_prio_gtthan(locklisthead, lock_list_metadata, task);
}


static inline tid_t LK_list_next(plist_t *locklisthead, tid_t task)
{
	return LL_next_elem(locklisthead, lock_list_metadata, task);
}


#ifdef TIROSINT_DATA_DEBUG
void osint_getlistdata(trlistdata_t* lstdata)
{
	if (lstdata) {
		lstdata->readylisthead = readylist;
		lstdata->waitlisthead  = waitlist;
		lstdata->rdywt_listmeta = rdywt_list_metadata;		
		lstdata->lock_listmeta = lock_list_metadata;
	}
}
#endif


#else
#error "TIROS_PRIO_SORT has illegal value in configuration."
#endif






#endif








